package algorithm;

import java.util.Arrays;

/**
 * @description: 类描述
 * @author: Fesine
 * @createTime:2017/7/31 22:36
 * @update:修改内容
 * @author: Fesine
 * @updateTime:2017/7/31 22:36
 */
public class InsertionSort {

    /**
     * 直接插入排序算法实现：后面与前一个比较，将小的左移
     * 算法描述：对于给定的一个数组，
     * 初始时假设第一个记录自成一个有序序列，
     * 其余记录为无序序列。
     * 接着从第二个记录开始，
     * 按照记录的大小依次将当前处理的记录插入到其之前的有序序列中，
     * 直至最后一个记录插入到有序序列中为止。
     * 平均O(n^2),最好O(n),最坏O(n^2);空间复杂度O(1);稳定;简单
     * 3 6 4 2 11 10 5
     * 3 6 4 2 11 10 5
     * 3 4 6 2 11 10 5
     * 2 3 4 6 11 10 5
     * 2 3 4 6 10 11 5
     * 2 3 4 5 6 10 11
     *
     * @param sorted
     */
    public static void straightInsertionSort(int[] sorted) {
        int tmp;
        //从第二个数据开始
        for (int i = 1; i < sorted.length; i++) {
            for (int j = i; j > 0; j--) {
                if (sorted[j] < sorted[j - 1]) {
                    tmp = sorted[j - 1];
                    sorted[j - 1] = sorted[j];
                    sorted[j] = tmp;
                }
            }
        }
    }

    /**
     * 希尔排序算法实现
     * 算法描述：先将待排序序列的数组元素分成多个子序列，
     * 使得每个子序列的元素个数相对较少，
     * 然后对各个子序列分别进行直接插入排序，
     * 待整个待排序序列“基本有序”后，
     * 再对所有元素进行一次直接插入排序。
     * 平均O(nlogn),最坏O(nlogn);空间复杂度O(1);不稳定;较复杂
     * 3 6 4 2 11 10 5
     * n=7 d =n/2=3
     * 2 6 4 3 11 10 5
     * 3 6 4 2 11 10 5
     * d=1
     * @param sorted
     */
    public static void shellInsertionSort(int[] sorted) {
        int n = sorted.length;//7
        int d = n / 2;//3
        while (d > 0) {
            System.out.println(d);
            //3 4
            for (int i = d; i < n; i++) {
                int j = i - d; //0 1
                while (j >= 0 && sorted[j] > sorted[j+d]) {
                    int tmp = sorted[j];
                    sorted[j] = sorted[j+d];
                    sorted[j+d] = tmp;
                    j = j - d; //-3
                }
            }
            d = d / 2;
        }
    }

    public static void main(String[] args) {
        int[] a = {3, 6, 4, 2, 11, 10, 5};
        straightInsertionSort(a);
        System.out.println(Arrays.toString(a));
        a = new int[]{1, 54, 6, 3, 78, 34, 12, 45, 56, 100};
        shellInsertionSort(a);
        System.out.println(Arrays.toString(a));
    }

}
